1. Field of the Invention
The present invention relates to a decoder that decodes a code by selecting a path out of paths representing transitions of each of states in a trellis diagram based on a predetermined condition, a decoder that decodes a code sequence encoded using a maximum-transition-run (MTR) code and an error correcting code, and an encoder that encodes an information sequence, and more particularly, to a decoder and a decoding method that can efficiently delete a path not satisfying a predetermined limitation to obtain a large gain without increasing a constraint length of a code.
2. Description of the Related Art
Conventionally, a technology called a partial-response-maximum-likelihood (PRML) system obtained by combining a partial-response (PR) system and a maximum-likelihood (ML) method has been developed as a data reproduction technique for a magnetic disk device (see, for example, Osawa, Okamoto, Saito, “Signal Processing Technology for High-Density Digital Magnetic Recording”, the Institute of Electronics, Information and Communication Engineers Transaction, C-II Vol. J81-C-II, No. 4, pp. 393-412, April 1998).
The partial-response System is a technology for realizing high density of information by introducing known intersymbol interference. For example, in a PR1 system (also referred to as the PR(1,1) system) that is a type of the partial-response system, a transfer characteristic 1+D (D represents a delay of 1 bit) is given to a record information sequence consisting of bits of “1” and “0” by a partial-response (PR) channel. In this case, a sum of a bit at time k and a bit at time k−1 is calculated to convert the record information sequence into a signal sequence taking three values of “0”, “1”, and “2”.
It is possible to extend the transfer characteristic of the partial-response system in such a manner asa+bD+cD2+dD3+ . . .A value obtained by adding one to a highest order of this transfer characteristic is referred to as a PR constraint length. For example, the PR constraint length is two in the PR1 system, and three in a PR2 system (also referred to as the PR(1,2,1) system, a transmission characteristic of which is 1+2D+D2).
The maximum-likelihood method is a decoding method of defining a state that can be taken within an infinite time, selecting a most likely transition in temporal transitions of the state, and outputting an input sequence corresponding to the selected transition as a decoded sequence.
FIG. 26 is a state transition table in a conventional PR1ML system obtained by combining the PR1 system and the maximum-likelihood method. FIG. 27 is a trellis diagram in the conventional PR1ML system.
The state transition table is a table of a correspondence relation between transitions of a state S0 corresponding to an input signal “0” and a state S1 corresponding to an input signal “1” and a value of a decoder input (also referred to as a decoding expected value). In the table, dkmn represents a value of a decoder input at the time when a state transitions from a state Sm at time k−1 to a state Sn at time k. The trellis diagram represents transitions of the states S0 and S1 as a diagram.
In the Viterbi decoding method, taking into account state transitions in the past based on the trellis diagram, a most likely path is selected by comparing paths transitioning to the present state. FIG. 28 is a diagram for explaining path selection processing using the conventional Viterbi decoding method.
As shown in FIG. 27, in the state S0 at time k, there are paths that transition from the state S0 and the state S1 at time k−1. In the Viterbi decoding method, a likely path is selected by calculating path metrics, that is, square Euclidian distances in the two paths. The same processing is executed on the state S1 at time k. After ending the path selection processing, a path memory holds information on the states S0 and S1 at transition sources in the selected path.
When paths are selected in this way, the paths merge at certain time. For example, in FIG. 28, paths merge at time k−5 and time k−1. When the paths merge in this way, a path at time before the merger is decided to be unified. This unified path is called a survival path. The survival path is outputted as a decoding result.
FIG. 29 is a diagram of the functional constitution of the conventional maximum-likelihood decoder. This maximum-likelihood decoder includes a BM calculating unit 1, an ACS calculating unit 2, a path memory 3, and a PM memory 4.
The BM calculating unit 1 calculates a likelihood called a branch metric (BM) with respect to a sample value (a signal obtained by adding noise of a channel to a decoder input).
The ACS calculating unit 2 performs an ACS (ADD, COMPARE, SELECT) operation for adding up a path metric in a state at time k−1 and a branch metric at the time when a state transitions from time k−1 to time k and selecting a path through comparison of magnitudes of path metrics in the state at time k obtained by the addition.
The path memory 3 stores information on a selected path. Since two paths extend from one state, for example, “0” is allocated to a path in the upper part and “1” is allocated to a path in the lower part in the trellis diagram shown in FIG. 27 to specify a selected path.
The PM memory 4 stores a path metric (PM) calculated by the ACS calculating unit 2 to use the path metric in an ACS operation at the next time.
A maximum-transition-run (MTR) code that limits the number consecutive transitions in such a maximum-likelihood decoder using the Viterbi decoding method has been developed. When the MTR code is used, it is possible to control a recording frequency and prevent occurrence of consecutive errors peculiar to the high-order PRML system.
For example, as a type of an extended-partial-response 4 maximum-likelihood (EPR4ML) system that is the PRML system, a PR constraint length of which is 4, there is a 6/7 MTR encoding EPR4ML system to which a 6/7 MTR code for limiting three consecutive transitions “0101” and “1010” in codes is applied (see, for example, B. Brickner, J. Moon, “Design of a Rate 6/7 Maximum Transition Run Code”, IEEE Transactions on Magnetics, Vol. 33, No. 5, September 1997).
FIG. 30 is a diagram for explaining the 6/7 MTR encoding EPR4ML system. In FIG. 30, trellis diagrams representing transitions from states Sm (m=0 to 7) at time k−1 to states Sn (n=0 to 7) at time k are shown with respect to the EPR4ML system and the 6/7 MTR encoding EPR4ML system, respectively. In the figure, ak represents a decoded value at time k.
In the EPR4ML system, since there is a path that transitions from the state S2 to the state S5, three consecutive transitions “0101” occur. However, in the 6/7 MTR encoding EPR4ML system, since a path that transitions from the state S2 to the state S5 (this path is represented by a bit “1”) is deleted (path cut) based on information on a bit string “010” representing the prior state S2, it is possible to prevent occurrence of the three consecutive transitions. When the path is deleted, since there is only one path leading to the state S5, path selection processing is not performed.
Similarly, in the EPR4ML system, since there is a path that transitions from the state S5 to the state S2, three consecutive transitions “1010” occur. However, in the 6/7 MTR encoding EPR4ML system, since a path that transitions from the state S5 to the state S2 (this path is represented by a bit “0”) is deleted based on information on a bit string “101” representing the prior state S2, it is possible to prevent occurrence of the three consecutive transitions.
It is desirable that a limit length of a consecutive transition is as small as possible and an encoding rate is as high as possible. However, actually, a logical limit is present. A 16/17 MTR code has been developed as an MTR code for limiting four consecutive transitions (see, for example, T. Nishiya, K. Tsukano, T. Hirai, S. Mita, T. Nara, “Rate 16/17 Maximum Transition Run (3;11) Code on an EEPRML Channel with an Error-Correcting Postprocessor”, IEEE Transactions on Magnetics, Vol. 35, No. 5, September 1999).
By using such a method, it is possible to remove all patterns in which a signal sequence “010 . . . ” is misunderstood as a signal sequence “101 . . . ” or all patterns in which a signal sequence “101 . . . ” is misunderstood as a signal sequence “010 . . . ”. It is possible to improve a gain of a signal.
However, in the conventional technologies, the number of states of the maximum-likelihood decoder that prevents occurrence of a consecutive transition with a length L, has to be set to 2L or more. In general, the number of states of a maximum-likelihood decoder depends on a PR constraint length. In other words, to prevent occurrence of the consecutive transition with a length L, it is necessary to set the PR constraint length larger than a consecutive transition limit length to satisfy a condition for the number of states. For example, in the MTR code that prohibits the three consecutive transitions, it is necessary to set the PR constraint length to 4 and set the number of states of the maximum-likelihood decoder to 2(4−1)=8.
When the PR constraint length of the maximum-likelihood decoder increases, a circuit size of the maximum-likelihood decoder markedly increases. For example, when the PR constraint length increases by 1, the circuit size is doubled. Therefore, it is important to efficiently delete a path that does not satisfy limitations such as the consecutive transition limit length to obtain a large gain without increasing the PR constraint length.